// HJ24 [最长递增子序列] 合唱队
// https://www.nowcoder.com/practice/6d9d69e3898f45169a441632b325c7b4
//出列多少位同学，剩下的同学合唱队形 longest-increasing-subsequence
// N 位同学站成一排，音乐老师要请最少的同学出列，使得剩下的 K
// 位同学排成合唱队形。 设K位同学从左到右依次编号为 1，2…，K
// ，他们的身高分别为T_1,T_2,…,T_KT 若存在i(1≤i≤K)
// 使得T_1<T_2<......<T_{i-1}<T_iT 则称这K名同学排成了合唱队形。
// 通俗来说，能找到一个同学，他的两边的同学身高都依次严格降低的队形就是合唱队形。
// 例子：123 124 125 123 121 是一个合唱队形
// 123 123 124 122不是合唱队形，因为前两名同学身高相等，不符合要求
// 123 122 121 122不是合唱队形，因为找不到一个同学，他的两侧同学身高递减。
// 你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
// 注意：不允许改变队列元素的先后顺序 且 不要求最高同学左右人数必须相等
// 输入用例两行数据，第一行是同学的总数 N ，第二行是 N 位同学的身高，以空格隔开
// 输出最少需要几位同学出列
// 输入 8
// 186 186 150 200 160 130 197 200
// 输出 4
// 由于不允许改变队列元素的先后顺序，
// 所以最终剩下的队列应该为186 200 160 130或150 200 160 130
// 思路：就是求剩下最多人，从左到右求递增序列的，从右到左求单调递增序列，二者和最大就是剩下最多
// 考虑合唱团中间最高的人，其与前面若干位组合成递增子序列、与后面若干位组合成递减子序列
// 两个数组：dp1[]表示以第i位结尾的最长递增子序列长度，dp2[]表示以第i位结尾的反向最长递增子序列长度
// 那么以第i位为最高的合唱团长度为  dp1[i]+dp2[i]，采取动态规划获得最大值即可
//
// 使用正序遍历“身高数组”，得到第一个dp_h[]数组。其中dp_h[ i
// ]表示从第0位到第i位， 这之中以第i位结尾的最长递增子序列包含的元素的个数。
// 对于dp_h[i]，是从dp_h数组中在它之前的所有元素中，找到小于对应“身高值”的最大dp值最大的那个，
// 因此我们有：dp_h[i]=max(dp_h[j]+1, dp_h[i])
// 使用逆序遍历“身高数组”，得到第二个dp_t[]数组。其中dp_t[i]表示从第n−1位到第i位，
// 这之中以第i位开头的最长递减子序列包含的元素的个数。
// 对于dp_t[i]，是从dp_t数组中在它之后的所有元素中，找到小于对应“身高值”的dp值最大的那个，
// 因此我们有 dp_t[i]=max(dp_t[j]+1, dp_t[i])
// 对两个dp数组中的值进行按序加和减去一，并求最大值，代表一个子序列先递增后递减并且具有的最大的长度；
// 用n减去这个最大长度获得最少的需要出列的人数。

#include <iostream>
using namespace std;
int main() {
  int nTotal = 0;
  int m[10000] = {0};
  int dp1[10000], dp2[10000];
  while (cin >> nTotal) {
    // 正序
    for (int i = 0; i < nTotal; i++) {
      cin >> m[i];
      dp1[i] = 1;
      for (int j = 0; j < i; j++) {
        if (m[i] > m[j]) {
          dp1[i] = max(dp1[i], dp1[j] + 1);
        }
      }
    }
    // 逆序
    for (int i = nTotal - 1; i >= 0; i--) {
      dp2[i] = 1;
      for (int j = nTotal - 1; j >= i; j--) {
        if (m[i] > m[j]) {
          dp2[i] = max(dp2[i], dp2[j] + 1);
        }
      }
    }
    // 求和得到最长先增后减子序列的长度
    int mn = 0;
    for (int i = 0; i < nTotal; i++) {
      if (dp1[i] + dp2[i] - 1 > mn) mn = dp1[i] + dp2[i] - 1;
    }
    cout << nTotal - mn << endl;
  }
  return 0;
}
